package sort.memory;

/**
 * 堆排序
 * 基于选择排序，不稳定排序，分为大根堆、小根堆，比快速排序慢一个常数因子，但是堆排序最适合外排序，因为它建堆很快
 * 左节点2i+1，右节点2i+2，最后一个非叶子节点为：arr.length/2 - 1
 * 算法思想：
 * 		将无序序列构建成一个大顶堆。从最后一个非叶子节点开始，比较是否大于子节点，不大于和的话，就和最大的子节点交换，然后递归看交换了的子节点是否满足堆，否则就开始第二个非叶子的判断
 * 		将堆顶元素和末尾元素交换，第二次就和倒数第二个元素交换
 * 		重新调整堆结构，然后重复上面两个步骤
 * @author：涂有
 * @date 2017年11月27日 下午3:50:09
 */
public class HeapSort {

	public static void sort(int a[]){
		buildHeap(a, a.length);
		for(int i = a.length - 1; i >= 0; i--){
			SortUtil.swap(a, 0, i); //把最大放到数组倒数第n个，第一轮就是倒数第一个
			slideDown(a, i, 0); //重新下拉跟节点
		}
	}
	
	public static void buildHeap(int a[], int heapSize){
		for(int i = heapSize>>1 - 1; i >= 0; i--){
			slideDown(a, heapSize, i);
		}
	}
	
	public static void slideDown(int a[], int heapSize, int index){
		if(index > heapSize>>1 - 1) return;  //如果是叶子节点就退出
		int left = index<<1 + 1;
		int right = index<<1 + 2;
		if(left < heapSize){ //首先判断左节点，左节点>=最后一个位置的话，右节点就肯定不存在
			if(right < heapSize){ //既有左节点又有右节点
				if(a[index] < a[left] && a[left] >= a[right]){
					SortUtil.swap(a, index, left);
					slideDown(a, heapSize, left);
				}else if(a[index] < a[right] && a[right] > a[left]){
					SortUtil.swap(a, index, right);
					slideDown(a, heapSize, right);
				}
			}else if(a[index] < a[left]){  //只有左节点的情况
				SortUtil.swap(a, index, left);
				slideDown(a, heapSize, left);
			}
		}
		
	}
}
